package leetcode;

/**
 * 买股票的最佳时机
 * 算法 :
 *   双重循环 --- 超时了
 *     第一层循环表示买入股票，第二层循环表示卖出股票
 *   动态规划
 *     使用 dp 数组存储前 i 天股票的最小值
 *     动态规划中的 dp 数组不一定要存结果
 *     这题也可以不用数组去存最小值，只要用一个变量即可
 */
public class _121 {
    public static void main(String[] args) {
        System.out.println(new _121().maxProfit_perfect_2(new int[]{7, 1, 5, 3, 6, 4}));
    }

    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 0; i < prices.length - 1; ++i) {
            for (int j = i + 1; j < prices.length; ++j) {
                ans = Math.max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }

    public int maxProfit_perfect(int[] prices) {
        int ans = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            ans = Math.max(ans, prices[i] - min);
        }
        return ans;
    }

    public int maxProfit_perfect_2(int[] prices) {
        int ans = 0;
        int[] dp = new int[prices.length];
        for (int i = 0; i < prices.length; i++) {
            if (i == 0) {
                dp[i] = prices[i];
                continue;
            } else {
                dp[i] = Math.min(dp[i - 1], prices[i]);
            }
            ans = Math.max(ans, prices[i] - dp[i]);
        }
        return ans;
    }

}
